package top.lywivan.dp;

/**
 * @author :lyw.ivan
 * @date :Created in 2022/8/6
 * @description : 0-1背包问题
 * @version: 1.0
 */
public class BackPack {

    /**
     * 获取背包能装的物品的最大价值，基于dp实现
     * @param wt 每个物品的重量
     * @param v 每个物品的价值
     * @param N 物品的个数
     * @param W 背包的最大容量
     * @return
     */
    public int dp(int[] wt,int[] v,int N,int W){
        //定义dp数组，dp[i][j]表示在背包容量为j，物品取前i个的情况下，背包中的物品的最大价值
        int[][] dp=new int[N+1][W+1];
        //初始化dp数组
        for(int i=0;i<=N;i++){
            dp[i][0]=0;
        }
        for(int i=0;i<=W;i++){
            dp[0][i]=0;
        }
        //进行状态转移
        for(int i=1;i<=N;i++){
            for(int j=1;j<=W;j++){
                //如果wt[i-1]过大，导致背包都装不下，那么当前物品必然不会放入背包
                if(wt[i-1]>j){
                    //此时从dp[i-1][j]转移过来即可
                    dp[i][j]=dp[i-1][j];
                }else {
                    //可以放入背包，但不一样要放
                    //不放背包时，从dp[i-1][j]转移过来，放入背包时，从dp[i-1][j-wt[i-1]]+v[i-1]转移过来
                    dp[i][j]=Math.max(dp[i-1][j],dp[i-1][j-wt[i-1]]+v[i-1]);
                }
            }
        }
        return dp[N][W];
    }

    /**
     * 测试用例
     * @param args
     */
    public static void main(String[] args) {
        int N = 3, W = 5; // 物品的总数，背包能容纳的总重量
        int[] w = {3, 2, 1}; // 物品的重量
        int[] v = {5, 2, 3}; // 物品的价值
        System.out.println(new BackPack().dp(w,v,N,W));
    }
}
